
\section{Related Work}

% Plateau structures studied by others
%Search space topology and 
Plateaus during search have been well studied for 
both SAT and CSP problems~\cite{Hampson93plateausand}. In SAT and CSP problems, 
a plateau is defined as a set of neighboring variable assignments that lead 
to the same number of unsatisfied constraints or clauses~\cite{Frank97whengravity,aima}. 
% Plateau and search topology in planning
Plateau structures have also been studied in planning under the context
of local search. A detailed analysis on why 
some planning problems are simple and how long 
the maximum exiting distance is in enforced
hill-climb are presented in~\cite{Hoffmann02}. 
G-value plateau in planning has also been studied in~\cite{gvalue}.

% Many work has been done to reduce plateau exploration -- local search. 
Many works have been done to accelerate plateau exploration
for local search algorithms. In CSP and SAT,
tabu search~\cite{Glover:1997:TS:549765} 
can be used to avoid falling back to the same states on a plateau. 
WalkSAT~\cite{Kautz96pushingthe} is a random-walk based algorithm that can find 
an exit to escape from a local minima. 
% Citation

There are several lines of work to 
accelerate plateau exploration in best-first search. 
% 2. space reduction to reduce plateau size
First, space reduction techniques like preferred operations~\cite{Richter09} 
and partial order reduction~\cite{IJCAI09a,IJCAI09b} can effectively 
reduce the number of states explored by the search algorithm,
and subsequently reduce the number of states on a plateau. However, 
space reduction approaches are indirect approaches 
to accelerate plateau exploration. These approaches 
cannot efficiently accelerate plateau exploration when 
preferred operators or partial order 
reductions are not effective. 
% 3. multiple heuristics to accelerate plateau escaping
Second, multiple heuristic functions 
can be used to sort states in the {\em open} list 
in different orders~\cite{helmert06}. 
Since different heuristic functions have different search topologies, 
when one heuristic function becomes uninformative
on its value plateau, other heuristics may give informative 
guidance and find exits on a plateau. However, extra heuristic function calculations 
and extra open lists can increase the overall time and space complexity 
of the search algorithm. 
% 4. Monte Carlo random walks MRW
Third, Monte Carlo random walk (MRW) algorithms have been used to 
solve planning problems with good performance~\cite{Nakhost09}. 
It is capable of escaping from local minima. However, it 
is slower comparing to deterministic best-first search when 
heuristic functions are informative. 


% 1. improving the quality of heuristic function
\nop{
Theoretically, one of the most efficient way 
to reduce the plateau size is to make heuristic 
function more accurate. However, it is infeasible
in practice to have a perfect heuristic function. 
}


%In addition,  on problems with a large ratio of dead end states, MRW procedure 
% rolls back to a stochastic hill climbing . 

% Our approach and the advantages
% TODO: state some advantages here @priority(low)
Our proposed random-walk assisted best-first search (RW-BFS) for planning 
is inspired by both the MRW approach and 
multiple heuristic search approach. 
We use a best-first search procedure for planning 
to conduct state space search for 
most of the time, as best-first search gives 
good performance when the heuristic functions 
are informative. In addition, under certain 
conditions, a random-walk procedure 
is invoked to assist the best-first search. 


